
from typing import Optional, Generator
import time 


class TreeNode:
    def __init__(self, 
                 attr: dict,
                 left: Optional["TreeNode"]=None,
                 right: Optional["TreeNode"]=None):
        self.attr = attr 
        self.left = left 
        self.right = right

    def prefixTraversal(self) -> Generator["TreeNode", None, None]:
        return NaiveTree(self).prefixTraversal()
    
    def inorderTraversal(self) -> Generator["TreeNode", None, None]:
        return NaiveTree(self).inorderTraversal()
    
    def postorderTraversal(self) -> Generator["TreeNode", None, None]:
        return NaiveTree(self).postorderTraversal()

class NaiveTree:
    def __init__(self, root: TreeNode):
        self.root = root 
    
    def prefixTraversal(self) -> Generator[TreeNode, None, None]:
        stack = [self.root]
        while stack:
            curr = stack.pop()
            yield curr
            
            if curr.right:
                stack.append(curr.right)
            
            if curr.left:
                stack.append(curr.left)
                
    def inorderTraversal(self) -> Generator[TreeNode, None, None]:
        stack: list[TreeNode] = []
        curr = self.root
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left 
            
            curr = stack.pop()
            yield curr 
            
            curr = curr.right
            
    def postorderTraversal(self) -> Generator[TreeNode, None, None]:
        stackin: list[TreeNode] = []
        
        while root or stackin:
            while root:
                stackin.append(root)
                root = root.left if root.left else root.right 
            
            curr = stackin.pop()
            yield curr
            if stackin and stackin[-1].left == curr:
                root = stackin[-1].right 
            else:
                root = None 
            
        
                
            
            
            
            
            
                
        
    
if __name__ == '__main__':
    root = TreeNode(attr=dict(value=1))
    root.left= TreeNode(attr=dict(value=2))
    root.right= TreeNode(attr=dict(value=3))
    root.left.left= TreeNode(attr=dict(value=4))
    root.left.right = TreeNode(attr=dict(value=5))
    
    for i in root.postorderTraversal():
        print(i.attr)
        time.sleep(0.3)

            
        

    